Users are demanding increased performance of their applications running on their computers. Computer hardware, including central processing units (CPUs), are becoming increasingly faster. However, their performance is limited by the speed at which data is available to be processed. There are several devices that provide the data. Disk drives, compact disks and other secondary storage devices can store great amounts of data cost effectively, but have great delays in providing data because the physical media on which the data is stored must be moved to a position where it can be read. This type of physical motion requires great amounts of time when compared to the cycle times of processors. The next fastest common data storage device is referred to as random access memory (RAM) which is much faster. However, processor speeds have increased, and even RAM cannot provide data fast enough to keep up with them.
In a typical computer, Level 1 (L1) and Level 2 (L2) cache memories are similar to RAM, but are even faster, and are physically close to a processor to provide data at very high rates. The cache memory is typically divided into 32, 64, or 128 byte cache lines. The size of a cache line normally corresponds to a common unit of data retrieved from memory. When data required by a processor is not available in L1 cache, a cache line fault occurs and the data must be loaded from lower speed L2 cache memory, or relatively slow RAM. The application is often effectively stalled during the loading of this data, and until such time as the data is available to the CPU. By decreasing the number of cache faults, an application will run faster. There is a need to reduce the number of cache line faults and provide data to processors even faster to keep applications from waiting.
Computer applications utilize data structures which are sometimes implemented as classes which are instantiated as objects. Classes define containers of data or information and code which operates on the data in response to method calls from other users or classes. Some classes can be very large, and take up several cache lines. The amount of each class actually used may be significantly less than the amount of data stored in the class. If the entire class is recalled from storage, even though only a small part of it is actually needed, many cache line misses will occur due to them containing unneeded data from the objects. Since there are a limited number of cache lines available for use by an application, it is important to use them efficiently. If there is insufficient space available for the desired data, time is spent in obtaining the data from slower storage and then populating the cache lines so the desired data is more quickly available to the processor.
There is a need for a better way to manage the cache lines so that data commonly needed by applications is available with a minimal amount of cache line misses.